package sort;

import util.Comparator;

/**
 * 快排 3.0
 * 空间复杂度 O(log N) 是长期期望的值，最差为 O（N）
 * <p>
 * 快排 1.0  =>   分 小于等于区 和 大于区 两个区 => 不稳定：例子： 67663， 划分值位5，则 3 < 5, 3和第一个 6交换，就会破坏稳定性
 *
 * @author Liaorun
 */
public class QuickSort implements Sortable {


    public static void main(String[] args) {
        Comparator comparator = new Comparator(10, 10);

        comparator.start(new QuickSort());
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        quickSort(arr, 0, arr.length - 1);
    }


    /**
     * arr[l..r]排好序
     */
    private static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            // 随机选择一个值为划分值，防止人为构造的差数据情况，保证时间复杂度的期望为 O(n * logn)
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            // 左边的小于区进入递归排序
            quickSort(arr, l, p[0] - 1);
            // 右边边的大于区进入递归排序
            quickSort(arr, p[1] + 1, r);
        }
    }

    /**
     * 这里一个处理arr[l..r]的函数
     * 默认已arr[r]做划分，arr[r] -> p
     * 返回等于区域（左边界，有边界），所以返回一个长度为2的数组res, res[0] res[1]
     */
    private static int[] partition(int[] arr, int i, int r) {
        // 小于区右边界
        int less = i - 1;

        // 大于区右边界
        int more = r;

        // l 表示当前数的位置 arr[r] 是 划分值
        // 当当前值的下标等于大于区的左边界时，跳出循环
        while (i < more) {
            // 当前值 < 划分值
            if (arr[i] < arr[r]) {
                // 当前值和小于区右边的数交换
                // i++
                swap(arr, ++less, i++);
            } else if (arr[i] > arr[r]) {
                // 当前值 > 划分值
                // 大于区前一个和当前值交换
                swap(arr, --more, i);
            } else {
                // 当前值等于 划分值，什么都不做
                // 需要比较下一个值
                i++;
            }
        }
        // 排完序后，划分值换到大于区的左边界
        swap(arr, more, r);

        // 返回等于区的范围
        return new int[]{less + 1, more};
    }

    public static void swap(int[] arr, int i, int r) {
        // 为什么存在交换同一个位置的值的情况
//        arr[i] = arr[r] ^ arr[i];
//        arr[r] = arr[r] ^ arr[i];
//        arr[i] = arr[r] ^ arr[i];

        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
    }

    @Override
    public void sort(int[] arr) {
        quickSort(arr);
    }

    @Override
    public void sort(int[] arr, int k) {

    }
}
